> > > > > 1. 25 iterations of DES with the first 8 bytes of the > > > > password as key, followed by 25 iterations of DES > > > > with the second 8 bytes of password as key. > > You've obviously got something else in mind. By all means, please tell > me how you're going to do it in 2^32 DES steps (still 2^35 (32 GB) bytes of > storage, a non-trivial sum.) Details and crypto-babble welcome:) > Ok, here's the explanation. I'd love to hear feedback about whether this is on charter for bugtraq; if it's not, email me and I'll avoid spamming y'all in the future. The hash function (1) above takes the all 0 plaintext block, encrypts it 25 times under 8 bytes of password W, and then encrypts that 25 times under the other 8 bytes of password W', producing the ciphertext C = Encrypt^25(W', Encrypt^25(W, 0)). The conceptually simplest attack works like this: 1. Generate ~ 2^32 random 8 byte keys K_i and store A_i = Encrypt^25(K_i, 0) in a hash table. 2. Generate ~ 2^32 random 8 byte keys K'_j and store B_j = Decrypt^25(K'_j, C) in the same hash table. 3. Find any match where A_i = B_j; then K_i, K'_j will work as a valid 16 byte password, since Encrypt^25(K'_j, Encrypt^25(K_i, 0)) = Encrypt^25(K'_j, A_i) = Encrypt^25(K'_j, B_j) = C. [Note that in all probability (K_i, K'_j) != (W, W'); but with this hash we don't need to find the exact password the user picked, just any one which gives the same hash output.] By the birthday paradox, there will be a match in step 3 above with probability about 1/2 [since each A_i, B_j block is 64 bits wide and we generated ~ 2^32 values of each]. If we try twice we'll probably succeed. This requires ~ 2^38 DES ops and ~ 2^35 bytes of memory. As you noted, the memory requirements are a bit high here [unless you use an Exabyte tape or somesuch, blech]. Also, it doesn't parallelize very nicely. Fortunately, the algorithm can be improved. Wiener and Oorschot have discovered an (elegant!) algorithm which will do the birthday attack with ~ 2^38 DES ops and negligible amounts of memory; it also works great in parallel. It's a nifty method for detecting cycles in periodic functions. See below for a reference. I have implemented their new algorithm, so I can say with experience that it really is a damn efficient piece of machinery. For example, I used it to find this non-trivial collision in Unix's crypt(3) hash: crypt("2NGGMda3", "Hx") = "yX8CL2luKyI" crypt("gnB9Gw1j", "s8") = "yX8CL2luKyI" [after removing the salt which crypt(3) prepends to its output] This does *NOT* break crypt(3)! It's a totally useless result, but it proved to me that the algorithm works well. It took a total of 6.1 billion trial crypt()s using the spare CPU time on 27 Sun workstations (LXs and Sparc 2s). I got about 1310 crypts per second, so I figure it took about 1290 CPU hours, total. Thus, from this experience, I estimate one can run the birthday attack I described earlier to break the double-DES hash (1) with about 2600 CPU hours. This is far too small an amount: if a college student like me can put together enough compute power to invert the hash over a week or two with spare CPU cycles, the hash function is clearly insecure. I'm interested in hearing more information about the OSF/1 or Ultrix hash function -- is there any place where I can get source or anything? I have access to one OSF/1 box, but it doesn't have any man pages or anything on a crypt16(). % I'm not sure if I've got the reference 100% correct; % I got the conference title by email from Wiener, but % haven't been able to find it in our library. @inproceedings{parallel-cycle-search, author = {Paul C. van Oorschot and Michael J. Wiener}, title = {Parallel Collision Search with Application to Hash Functions and Discrete Logarithms}, booktitle = {2nd {ACM} Conference on Computer and Communications Security}, year = {1994} } I have a postscript version of this paper from the authors; if you can't find it in your library, you can probably get a copy from them. Better still, if they okay-ed it, I'd put the paper up for anonymous ftp somewhere... ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu